function lengthOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let dp = Array(len).fill(1);
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

function lengthOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let res = [nums[0]];
  for (let i = 1; i < len; i++) {
    let lastItem = res[res.length - 1];
    if (nums[i] > lastItem) {
      res.push(nums[i]);
    } else {
      let l = 0;
      let r = res.length - 1;
      while (l < r) {
        let mid = (l + r) >> 1;
        if (res[mid] < nums[i]) {
          l = mid + 1;
        } else {
          r = mid;
        }
      }
      res[l] = nums[i];
    }
  }

  return res.length;
}

function indexOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let res = [0];
  let prev = [undefined];
  for (let i = 1; i < len; i++) {
    let lastItem = nums[res[res.length - 1]];
    if (nums[i] > lastItem) {
      prev[i] = res[res.length - 1];
      res.push(i);
    } else {
      let l = 0;
      let r = res.length - 1;
      while (l < r) {
        let mid = (l + r) >> 1;
        if (nums[res[mid]] < nums[i]) {
          l = mid + 1;
        } else {
          r = mid;
        }
      }
      res[l] = i;

      if (l === 0) {
        prev[i] = undefined;
      } else {
        prev = [res[l - 1]];
      }
    }
  }

  let reslen = res.length;
  let prevIndex = res[reslen - 1];
  while (reslen > 0) {
    reslen--;
    res[reslen] = prevIndex;
    prevIndex = prev[prevIndex];
  }

  return res;
}
